import functools


class Solution:
    def strangePrinter(self, s: str) -> int:
        @functools.lru_cache(None)
        def dfs(i, j):
            if i > j:
                return 0

            # 单独打印第1个的情况
            ans = dfs(i + 1, j) + 1

            # 和后面的一起打印第1个的情况
            for k in range(i + 1, j + 1):
                if s[i] == s[k]:
                    ans = min(ans, dfs(i, k - 1) + dfs(k + 1, j))

            return ans

        return dfs(0, len(s) - 1)


if __name__ == "__main__":
    print(Solution().strangePrinter("aaabbb"))  # 2
    print(Solution().strangePrinter("aba"))  # 2

    # 测试用例40/200
    print(Solution().strangePrinter("abcabc"))  # 5

    # 测试用例55/200
    print(Solution().strangePrinter("tbgtgb"))  # 4
